//队列
typedef int TYPE;
typedef struct QlistNode {
        struct QlistNode* next;
        TYPE date;
}QNode;
typedef struct Queue {
        QNode* front;//队头
        QNode* fear;//队尾
}Queue;

QNode* BuyNode(TYPE date);//节点的创建
void QueueInit(Queue* q);//初始化队列
void QueuePush(Queue* q, TYPE data);//队尾入队列
 void QueuePop(Queue* q);//队头出队列
 int QueueEmpty(Queue* q);//检测队列是否为空
 TYPE QueueFront(Queue* q);//获取队列头部元素
 TYPE QueueFear(Queue* q);//获取队列尾部元素
 int QueueSize(Queue* q);//获取队列中有效元素个数
 void QueueDestroy(Queue* q); //销毁队列


//节点的创建
QNode* BuyNode(TYPE date){
        QNode* new_node = (QNode*)malloc(sizeof(QNode));
        if (!new_node)
               assert(0);
        new_node->next = NULL;
        new_node->date = date;
        return new_node;
}
//初始化
void QueueInit(Queue* q) {
        QNode* head = BuyNode(0);
        q->front = head;
        q->fear = head;
        return;
}
//队尾入队列
void QueuePush(Queue* q, TYPE data) {
        assert(q);
        QNode* new_node = BuyNode(data);
        q->fear->next = new_node;
        q->fear = new_node;
        return;
}
//队头出队列
void QueuePop(Queue* q) {
        if (QueueEmpty(q))//检测是否为空
               return;
        QNode* del_node = q->front->next;
        q->front->next = del_node->next;
        //注意当只有一个有效元素时，将队尾指针指向头，否则将成为野指针
        if (del_node == q->fear)
               q->fear = q->front;
        free(del_node);
        return;
}
//检测队列是否为空
int QueueEmpty(Queue* q) {
        assert(q);
        return q->front == q->fear;
}
//获取队列头部元素
TYPE QueueFront(Queue* q) {
        if (QueueEmpty(q)) {
               printf("队列为空!\n");
               return -1;
        }
        return q->front->next->date;
}
//获取队列尾部元素
TYPE QueueFear(Queue* q) {
        if (QueueEmpty(q)){
               printf("队列为空!\n");
               return -1;
        }
        return q->fear->date;
}
//获取队列中有限元素个数
int QueueSize(Queue* q) {
        assert(q);
        int count = 0;
        QNode* cur = q->front->next;
        while (cur) {
               cur = cur->next;
               count++;
        }
        return count;
}
//销毁队列
void QueueDestroy(Queue* q) {
        assert(q);
        QNode* del_node = q->front->next;
        while (del_node) {
               q->front->next = del_node->next;
               free(del_node);
               del_node = q->front->next;
        }
        free(q->front);
        q->front = q->fear = NULL;
}
//////////////////////////////
typedef struct {
    Queue q1;
    Queue q2;
} MyStack;


MyStack* myStackCreate() {
    MyStack* stack = (MyStack*)malloc(sizeof(MyStack));
    if(!stack)
        assert(0);
    QueueInit(&stack->q1);
    QueueInit(&stack->q2);
    return stack;
}

void myStackPush(MyStack* obj, int x) {
    assert(obj);
    if(!QueueEmpty(&obj->q1))
        QueuePush(&obj->q1,x);
    else
        QueuePush(&obj->q2,x);
    return;
}

int myStackPop(MyStack* obj) {
    assert(obj);
    int ret = 0;
    if(!QueueEmpty(&obj->q1)){
        while(QueueSize(&obj->q1)>1){
            QueuePush(&obj->q2, QueueFront(&obj->q1));
            QueuePop(&obj->q1); 
        }
        ret = QueueFront(&obj->q1);    
        QueuePop(&obj->q1);
    }
    else{
        while(QueueSize(&obj->q2) > 1){
            QueuePush(&obj->q1,QueueFront(&obj->q2));
            QueuePop(&obj->q2);
        }
        ret = QueueFront(&obj->q2);    
        QueuePop(&obj->q2);
    }
    return ret;
}

int myStackTop(MyStack* obj) {
    assert(obj);
    if(!QueueEmpty(&obj->q1))
        return QueueFear(&obj->q1);
    else
        return QueueFear(&obj->q2);
}

bool myStackEmpty(MyStack* obj) {
    assert(obj);
    if(QueueEmpty(&obj->q1)&&QueueEmpty(&obj->q2))
        return true;
    return false;
}

void myStackFree(MyStack* obj) {
    assert(obj);
    QueueDestroy(&obj->q1);
    QueueDestroy(&obj->q2);
    free(obj);
}

/**
 * Your MyStack struct will be instantiated and called as such:
 * MyStack* obj = myStackCreate();
 * myStackPush(obj, x);
 
 * int param_2 = myStackPop(obj);
 
 * int param_3 = myStackTop(obj);
 
 * bool param_4 = myStackEmpty(obj);
 
 * myStackFree(obj);
*/